package com.favorite;

import java.util.List;

public class Solution148 {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode A = sortList(head);
        ListNode B = sortList(tmp);
        return merge(A, B);
    }

    public ListNode merge(ListNode A, ListNode B) {
        if (A == null) return B;
        if (B == null) return A;
        if (A.val <= B.val) {
            A.next = merge(A.next, B);
            return A;
        } else {
            B.next = merge(A, B.next);
            return B;
        }
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
